//1.模拟 --- Z字型变换
//解法一:暴力模拟
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;  // 特殊情况直接返回
        int len = s.size();
        vector<vector<char>> ret(numRows, vector<char>(len, '*'));
        int x = 0, y = 0;
        int i = 0;
        
        while(i < len) 
        {
            // 向下填充
            while(x < numRows && i < len) 
            {
                ret[x][y] = s[i++];
                x++;
            }
            x -= 2;
            y += 1;
            
            // 向上填充
            while(x >= 0 && i < len) 
            {
                ret[x][y] = s[i++];
                x--;
                y++;
            }            
            x += 2;
            y -= 1;
        }
        
        string r;
        for(int i = 0; i < numRows; i++) 
            for(int j = 0; j < len; j++) 
                if(ret[i][j] != '*') 
                    r += ret[i][j];
        return r;
    }
};

//解法二:找规律
//注意: 99%的模拟题要优化都是通过找规律
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        int d = 2 * numRows - 2;
        int len = s.size();
        string ret;
        //第0行
        for(int i = 0; i < len; i += d)
            ret += s[i];

        //第1-n-2行
        for(int k = 1; k < numRows - 1; k++)
        {
            for(int i = k, j = d - k; j < len || i < len; i += d, j += d)
            {
                if(i < len) ret += s[i];
                if(j < len) ret += s[j];
            } 
        }

        //第n-1行
        for(int i = numRows - 1; i < len; i += d)
            ret += s[i];
        return ret;
    }
};


//2.模拟 --- 外观数列
//解法一: 递归
class Solution {
public:
    string countAndSay(int n) {
        if(n == 1) return "1";
        string ret;
        string s = countAndSay(n - 1);
        int count = 1, i = 0;
        while(i < s.size())
        {
            while(i + 1 < s.size() && s[i] == s[i + 1])
            {
                count++;
                i++; 
            }
            ret += count + '0';
            ret += s[i]; 
            count = 1; 
            i++;
        }
        return ret;
    }
};

//解法二: 迭代
class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for(int i = 1; i < n; i++) //解释 i - 1次即可
        {
            int len = ret.size();
            string tmp;
            for(int l = 0, r = 0; r < len;)
            {
                while(r < len && ret[l] == ret[r]) r++;
                tmp += (to_string(r - l) + ret[l]);
                l = r;
            }
            ret = tmp;
        }  
        return ret; 
    }
};
